package leetcode_0480

import "sort"

func medianSlidingWindow(nums []int, k int) []float64 {

	var result []float64
	left, right, arr := 0, k-1, []int{}
	for i := 0; i < k; i++ {
		arr = append(arr, nums[i])
	}
	sort.Ints(arr)

	for {

		// 偶数
		if k%2 == 0 {
			result = append(result, float64(arr[k/2-1]+arr[k/2])/2)
		} else {
			result = append(result, float64(arr[k/2]))
		}

		left++
		right++

		if right >= len(nums) {
			break
		}

		arr = resort(arr, nums[left-1], nums[right])
	}

	return result
}

// 排序
func resort(arr []int, ori int, dest int) []int {

	length := len(arr)

	// 相等则不需要替换
	if ori == dest {
		return arr
	}

	index := binarySearch(arr, ori)
	arr[index] = dest

	// 比较挪动位置，保证数组有序
	if dest > ori {
		for index < length-1 && arr[index] > arr[index+1] {
			arr[index], arr[index+1] = arr[index+1], arr[index]
			index++
		}
	} else if dest < ori {
		for index > 0 && arr[index] < arr[index-1] {
			arr[index], arr[index-1] = arr[index-1], arr[index]
			index--
		}
	}

	return arr
}

// 二分查找
func binarySearch(arr []int, value int) int {

	low, high := 0, len(arr)-1

	for low <= high {
		mid := (low + high) / 2
		if arr[mid] < value {
			low = mid + 1
		} else if arr[mid] > value {
			high = mid - 1
		} else {
			return mid
		}
	}

	return -1
}
